package com.company.剑指offer每日刷题.专项版;

import java.util.Arrays;

/**
 * 题目：前 n 个数字二进制中 1 的个数
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 * 示例 1:
 *
 * 输入: n = 2
 * 输出: [0,1,1]
 * 解释:
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 说明 :
 *
 * 0 <= n <= 10^5
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/w3tCBm
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class CountBits {

    public static void main(String[] args) {
        CountBits obj = new CountBits();
        int[] ints = obj.countBits(5);
        System.out.println(Arrays.toString(ints));
    }

    /**
     *
     * 动态规划-最高有效位法
     * 思路： 1.定义：我们将一个二进制数中的除了最高有效位其他所有位上的数变成0，得到的这个数为最高有效位数。
     *      如：  1011的最高有效位数是 1000；  11101   的最高有效位数是 10000
     *      令 第i个数的最高有效位数是 hightBit  ，将第i个数中bit的个数表示为 bit[i]
     *      2.通过以上的定义，可得如下结论
     *          对于一个正整数x，它的最高有效位数是y，那么有一个正整数z满足
     *          z = x -y,  bit[x] = bit[z] +1
     *
     *      3.判断正整数y是否是其他数的最高有效位数，看是否满足
     *          y & (y -1) ==0
     *      4.得到状态转移方程：
     *      当 i=0， bit[i] = 0;
     *      当 i >0 ，bit[i] = bit[i-hightBit]+1
     * */
    public int[] countBits(int n) {
        int[] bit = new int[n+1];
        bit[0]=0;
        int higthBit=0;
        for(int i=1;i<=n;i++){
            if((i & (i -1)) == 0){
                higthBit =i;
            }
            bit[i] = bit[i-higthBit] +1;
        }
        return bit;
    }

}
